package leetcode.数学;

/**
 * 康托展开：给出 52413 求它是 [1,2,3,4,5] 全排列里面的第几个数
 * <p>
 * 逆康托展开：给出 [1,2,3,4,5] 求第 107 个排列是什么数
 * 应用题：
 * 1. Test60
 */
public class 康托展开 {

    /**
     * 输入一个整数，返回它是该数组全排列里面的第几个数
     *
     * @param n
     * @return
     */
    public static int cantorExpansion(int n) {
        int position = 0;
        String number = String.valueOf(n);
        for (int i = 0; i < number.length(); i++) {
            position += (getMinCount(number.charAt(i), number, i) * getFactorial(number.length()-i-1));
        }
        return position + 1;
    }

    // 求小于等于 x 的数有几个，且排除已经处理过的数
    public static int getMinCount(char x, String number, int index) {
        Integer num = Integer.valueOf(String.valueOf(x));
        for (int i = 0; i < index; i++) {
            Integer tmp = Integer.valueOf(String.valueOf(number.charAt(i)));
            if (tmp < num) {
                num--;
            }
        }
        return num - 1;
    }

    // 求x的阶乘
    public static int getFactorial(int x) {
        if (x == 0)
            return 1;
        int res = x;
        for (int i = 1; i < x; i++) {
            res *= i;
        }
        return res;
    }



    public static void main(String[] args) {
        System.out.println(cantorExpansion(52413)); // 107
        System.out.println(cantorExpansion(312)); // 5
        System.out.println(cantorExpansion(34125)); // 61
    }
}
